import java.util.*;

public class test {
    public static void main(String[] args) {
        System.out.println(SolutionOffrequencySort.frequencySort("Aabb"));
    }

    class SolutionOfcountPairs {
        int MOD = 1000000007;

        public int countPairs1(int[] deliciousness) {
            int res = 0, len = deliciousness.length;
            for (int i = 0; i < len - 1; i++) {
                for (int j = i + 1; j < len; j++) {
                    int sum = deliciousness[i] + deliciousness[j];
                    // 判断是否为2的n次幂，x & (x - 1) == 0（2幂次数的二进制1的个数只有一个），要注意和为0的情况
                    if ((sum & (sum - 1)) == 0 && sum != 0) {
                        res = (res + 1) % MOD;
                    }
                }
            }
            return res;
        }

        public int countPairs(int[] deliciousness) {
            int maxVal = 0;
            for (int val : deliciousness) {
                maxVal = Math.max(maxVal, val);
            }
            int maxSum = maxVal * 2; // 任意两个元素之和都不会超过maxVal × 2
            int pairs = 0;
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            int n = deliciousness.length;
            for (int i = 0; i < n; i++) {
                int val = deliciousness[i];
                for (int sum = 1; sum <= maxSum; sum <<= 1) { // sum表示小于maxSum的2的幂次数
                    int count = map.getOrDefault(sum - val, 0); // 记录已遍历部分与当前数和为幂次数的情况
                    pairs = (pairs + count) % MOD;
                }
                map.put(val, map.getOrDefault(val, 0) + 1);
            }
            return pairs;
        }
    }

    class SolutionOfdisplayTable {
        public List<List<String>> displayTable(List<List<String>> orders) {
            // 从订单中获取餐品名称和桌号，统计每桌点餐数量
            Set<String> nameSet = new HashSet<String>();
            Map<Integer, Map<String, Integer>> foodsCnt = new HashMap<Integer, Map<String, Integer>>();
            for (List<String> order : orders) {
                nameSet.add(order.get(2));
                int id = Integer.parseInt(order.get(1));
                Map<String, Integer> map = foodsCnt.getOrDefault(id, new HashMap<String, Integer>());
                map.put(order.get(2), map.getOrDefault(order.get(2), 0) + 1);
                foodsCnt.put(id, map);
            }
            // 提取餐品名称，并按字母顺序排列
            int n = nameSet.size();
            List<String> names = new ArrayList<String>();
            for (String name : nameSet) {
                names.add(name);
            }
            Collections.sort(names);

            // 提取桌号，并按餐桌桌号升序排列
            int m = foodsCnt.size();
            List<Integer> ids = new ArrayList<Integer>();
            for (int id : foodsCnt.keySet()) {
                ids.add(id);
            }
            Collections.sort(ids);

            // 填写点菜展示表
            List<List<String>> table = new ArrayList<List<String>>();
            List<String> header = new ArrayList<String>();
            header.add("Table");
            for (String name : names) {
                header.add(name);
            }
            table.add(header);
            for (int i = 0; i < m; ++i) {
                int id = ids.get(i);
                Map<String, Integer> cnt = foodsCnt.get(id);
                List<String> row = new ArrayList<String>();
                row.add(Integer.toString(id));
                for (int j = 0; j < n; ++j) {
                    row.add(Integer.toString(cnt.getOrDefault(names.get(j), 0)));
                }
                table.add(row);
            }
            return table;
        }
    }

    class SolutionOfcountOfAtoms {
        int i, n;
        String formula;

        public String countOfAtoms(String formula) {
            this.i = 0;
            this.n = formula.length();
            this.formula = formula;

            Deque<Map<String, Integer>> stack = new LinkedList<Map<String, Integer>>();
            stack.push(new HashMap<String, Integer>());

            StringBuffer res = new StringBuffer();
            for (int i = 0; i < formula.length(); ++i) {
                if (formula.charAt(i) == '(') { // 出现（）统计元素个数
                    while (formula.charAt(i) != ')') {

                    }
                }
            }
            return res.toString();
        }
    }

    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] res = new int[2];
        int[] flag = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            ++flag[nums[i]];
        }
        for (int i = 1; i <= n; ++i) {
            if (flag[i] == 2)
                res[0] = i;
            if (flag[i] == 0)
                res[1] = i;
        }
        return res;
    }

    static class SolutionOffrequencySort {
        public static String frequencySort(String s) {
            StringBuffer res = new StringBuffer();
            HashMap<Character, Integer> record = new HashMap<Character, Integer>();
            int len = s.length();
            for (int i = 0; i < len; ++i) {
                record.put(s.charAt(i), record.getOrDefault(s.charAt(i), 0) + 1);
            }
            List<Map.Entry<Character, Integer>> infoIds = new ArrayList<Map.Entry<Character, Integer>>(
                    record.entrySet());
            Collections.sort(infoIds, new Comparator<Map.Entry<Character, Integer>>() {
                public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                    return o1.getValue().compareTo(o2.getValue());
                }
            });
            for (int i = infoIds.size() - 1; i >= 0; --i) {
                for (int j = 0; j < infoIds.get(i).getValue(); ++j) {
                    res.append(infoIds.get(i).getKey());
                }
            }
            return res.toString();
        }
    }

    static class SolutionOffindMaxLength {

        // 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度

        public static int findMaxLength1(int[] nums) {
            // 暴力解法，超时，逐个元素开始顺序比较连续数组，前缀和两倍等于数组长
            int len = nums.length, ans = 0;
            for (int i = 0; i < len; ++i) {
                int sum = 0;
                for (int j = i; j < len; ++j) {
                    sum += nums[j];
                    if (sum * 2 == j - i + 1) {
                        ans = Math.max(ans, sum * 2);
                    }
                }
            }
            return ans;
        }

        public int findMaxLength(int[] nums) {
            // 前缀和+hash表
            // 1 计数加一，0 计数减一，这样可以知道到当前位置处之前的0，1出现情况
            // 若此时的计数情况同之前的有相同时，此时的连续数组减去之前连续数组情况，得到的统计值为0，及我们要找的情况
            int ans = 0, count = 0;
            Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
            indexMap.put(0, -1); // 需要加入一个0的情况，这时候没有遍历到任何一个元素，下标设置为-1
            for (int i = 0; i < nums.length; ++i) {
                count += nums[i] == 1 ? 1 : -1;
                if (indexMap.containsKey(count)) {
                    ans = Math.max(ans, i - indexMap.get(count));
                } else {
                    indexMap.put(count, i);
                }
            }
            return ans;
        }
    }

    static class SolutionOfcanEat {

        // favoriteTypei, favoriteDayi, dailyCapi
        // fDi > fTi，后面天数吃到前面的糖果，未到之前但吃到fTi时每天一颗糖果，看能否满足，未到之前未吃到fTi时，看情况
        // fDi < fTi，尽快吃到后面的糖果，与dCi相关
        public static boolean[] canEat(int[] candiesCount, int[][] queries) {
            int clen = candiesCount.length, qlen = queries.length;
            boolean[] ans = new boolean[qlen];
            int[] sum = new int[clen + 1];
            for (int i = 1; i <= clen; ++i)
                sum[i] = sum[i - 1] + candiesCount[i - 1];
            for (int i = 0; i < qlen; ++i) {
                long low = sum[queries[i][0]] / queries[i][2] + 1, high = sum[queries[i][0] + 1];
                ans[i] = low <= queries[i][1] + 1 && queries[i][1] + 1 <= high;
            }
            return ans;
        }
    }

    public static boolean isPowerOfFour(int n) {
        int count = -1, temp = n;
        while (temp != 0) {
            if (temp % 2 != 0 && temp != 1) {
                System.out.println(temp);
                return false;
            }
            temp /= 2;
            ++count;
            System.out.println(count);
        }
        return n > 0 && count % 2 == 0;
    }

    public static int solve(String a) {
        // write code here
        char[] ach = a.toCharArray();
        int ans = 0, len = ach.length;
        for (int i = 0; i < len / 2; ++i) {
            int j = i + 1;
            while (j <= len / 2) {
                if (ach[j] == ach[i]) {
                    boolean flag = true;
                    for (int index = 1; index <= j - i - 1; ++index) {
                        if (ach[index + i] != ach[index + j])
                            flag = false;
                    }
                    if (flag)
                        ans = Math.max(ans, 2 * (j - i));
                }
                ++j;
            }
        }
        return ans;
    }

    static class SolutionOfmaxUncrossedLines {

        public int maxUncrossedLines(int[] nums1, int[] nums2) {

            return nums1.length < nums2.length ? countLines(nums1, nums2) : countLines(nums2, nums1);
        }

        public int countLines(int[] nums1, int[] nums2) { // 假定nums1 < nums2
            int ans = 0, len1 = nums1.length, len2 = nums2.length;
            int[] dp = new int[len1];
            for (int i = 0; i < len1; ++i) {
                int j = 0;
                while (j < len2) {
                    if (nums1[i] == nums2[j])
                        break;
                    ++j;
                }
                dp[i] = j;
            }
            return ans;
        }
    }

    class SolutionOftopKFrequent {
        public List<String> topKFrequent(String[] words, int k) {
            int len = words.length;
            if (len == 0)
                return null;
            HashMap<String, Integer> record = new HashMap<String, Integer>();
            List<String> ans = new ArrayList<String>();
            for (String word : words) {
                record.put(word, record.getOrDefault(word, 0) + 1);
            }
            // 先记录下来所有的出现的单词
            for (Map.Entry<String, Integer> entry : record.entrySet()) {
                ans.add(entry.getKey());
            }
            // 然后比较每个单词的出现次数，将出现次数较多的单词放在前面
            Collections.sort(ans, new Comparator<String>() {
                public int compare(String word1, String word2) {
                    return record.get(word1) == record.get(word2) ? word1.compareTo(word2)
                            : record.get(word2) - record.get(word1);
                }
            });
            return ans.subList(0, k);
        }
    }

    class SolutionOfkthLargestValue {
        public int kthLargestValue(int[][] matrix, int k) {
            int m = matrix.length, n = matrix[0].length;
            int[][] pre = new int[m + 1][n + 1];
            List<Integer> results = new ArrayList<Integer>();
            for (int i = 1; i <= m; ++i) {
                for (int j = 1; j <= n; ++j) {
                    pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1];
                    results.add(pre[i][j]);
                }
            }

            Collections.sort(results, new Comparator<Integer>() {
                public int compare(Integer num1, Integer num2) {
                    return num2 - num1;
                }
            });
            // results.sort(Comparator.naturalOrder());
            // return results.get(results.size() - k);
            return results.get(k - 1);
        }
    }

    public class SolutionOfpermute {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

        public ArrayList<ArrayList<Integer>> permute(int[] nums) {
            if (nums == null || nums.length < 1)
                return res;
            Arrays.sort(nums);
            ArrayList<Integer> list = new ArrayList<Integer>();
            solve(list, nums);
            return res;
        }

        private void solve(ArrayList<Integer> list, int[] nums) {
            if (list.size() == nums.length) {
                res.add(new ArrayList<Integer>(list));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                if (!list.contains(nums[i])) { // 如果已经包含就不再加入---相当于剪纸啊？
                    list.add(nums[i]);
                    solve(list, nums);
                    list.remove(list.size() - 1);
                }
            }
        }
    }

    class SolutionOfcountTriplets {
        // a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
        // b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
        // 令a == b, 前提：a ^ b = 0，即arr[i] ^ ... ^ arr[k] = 0
        // 0 <= i < j <= k < len，找到满足的i和k，则j存在的取值情况为 k - i
        public int countTriplets(int[] arr) {
            int ans = 0, len = arr.length;
            int[] xors = new int[len + 1];
            for (int i = 0; i < len; i++) {
                xors[i + 1] = xors[i] ^ arr[i];
            }
            for (int i = 0; i < len - 1; ++i) {
                for (int k = i + 1; k < len; ++k) {
                    // xors[i] = arr[0] ^ ... ^ arr[i - 1]
                    // xors[k + 1] = arr[0] ^ ... ^ arr[i - 1] ^ ... ^ arr[i] ^ ... ^ arr[k]
                    // = xors[i] ^ 0，故xors[i] == xors[k + 1]即满足条件arr[i] ^ ... ^ arr[k] = 0
                    if (xors[i] == xors[k + 1]) {
                        ans += (k - i);
                    }
                }
            }
            return ans;
        }

        // hash表方式，实现一重循环
        public int countTripletsByHash(int[] arr) {
            int n = arr.length;
            Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
            Map<Integer, Integer> total = new HashMap<Integer, Integer>();
            int ans = 0, s = 0;
            for (int k = 0; k < n; ++k) {
                int val = arr[k];
                if (cnt.containsKey(s ^ val)) {
                    ans += cnt.get(s ^ val) * k - total.get(s ^ val);
                }
                cnt.put(s, cnt.getOrDefault(s, 0) + 1);
                total.put(s, total.getOrDefault(s, 0) + k);
                s ^= val;
            }
            return ans;
        }
    }

    static class SolutionOfintToRoman {
        static String[] thousands = { "", "M", "MM", "MMM" };
        static String[] hundreds = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
        static String[] tens = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
        static String[] ones = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };

        public static String intToRoman(int num) {
            StringBuffer roman = new StringBuffer();
            roman.append(thousands[num / 1000]);
            roman.append(hundreds[num % 1000 / 100]);
            roman.append(tens[num % 100 / 10]);
            roman.append(ones[num % 10]);
            return roman.toString();
        }
    }

    class SolutionOfintToRoman2 {
        int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
        String[] symbols = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

        public String intToRoman(int num) {
            StringBuffer res = new StringBuffer();
            for (int i = 0; i < values.length; ++i) {
                while (num >= values[i]) {
                    num -= values[i];
                    res.append(symbols[i]);
                }
                if (num == 0)
                    break;
            }
            return res.toString();
        }
    }

    class SolutionOfromanToInt {
        public int romanToInt(String s) {
            int res = 0;
            int preNum = getValue(s.charAt(0));
            for (int i = 1; i < s.length(); ++i) {
                int num = getValue(s.charAt(i));
                if (preNum < num) {
                    res -= preNum;
                } else {
                    res += preNum;
                }
                preNum = num;
            }
            res += preNum;
            return res;
        }

        private int getValue(char ch) {
            switch (ch) {
                case 'I':
                    return 1;
                case 'V':
                    return 5;
                case 'X':
                    return 10;
                case 'L':
                    return 50;
                case 'C':
                    return 100;
                case 'D':
                    return 500;
                case 'M':
                    return 1000;
                default:
                    return 0;
            }
        }
    }

    static class SolutionOfxorQueries {
        // Q[i] = [Li,Ri] = (a[Li] ^ a[Li+1] ^ … ^a[Ri])
        // dp[Li] = a[0]^a[1]^ … ^a[Li]
        // dp[Li - 1] = a[0]^a[1]^ … ^a[Li - 1]
        // dp[Ri] = a[0]^a[1]^ … ^a[Li] ^a[Li + 1]^ … ^a[Ri] = dp[Li] ^ a[Li + 1]^ …
        // ^a[Ri]
        // = dp[Li - 1] ^ a[Li] ^a[Li + 1]^ … ^a[Ri] = dp[Li - 1] ^ Q[i]
        // 由自反性 x^y^y = x 可知：
        // Q[i] = dp[Li - 1] ^ dp[Ri]
        public static int[] xorQueries(int[] arr, int[][] queries) {
            int len = arr.length, resLen = queries.length;
            int[] dp = new int[len], res = new int[resLen];
            dp[0] = arr[0];
            for (int i = 1; i < len; ++i) {
                dp[i] = arr[i] ^ dp[i - 1];
            }
            for (int i = 0; i < resLen; ++i) {
                if (queries[i][1] == queries[i][0])
                    res[i] = arr[queries[i][0]];
                else {
                    if (queries[i][0] == 0)
                        res[i] = dp[queries[i][1]];
                    else
                        res[i] = dp[queries[i][1]] ^ dp[queries[i][0] - 1];
                }
            }
            return res;
        }
    }

    public static String replaceSpace(String s) {
        StringBuffer sBuffer = new StringBuffer();
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == ' ') {
                sBuffer.append("%20");
            } else {
                sBuffer.append(s.charAt(i));
            }
        }
        return sBuffer.toString();
    }

    static class SolutionOfDecode {
        /**
         * 给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数
         * 
         * 它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 
         * 
         * 比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 
         * 
         * 给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一
         */
        // 注意perm为前n个正整数的排列
        public static int[] decode(int[] encoded) { // 暴力解法，超时
            int n = encoded.length + 1; // 奇数
            int[] perm = new int[n];
            for (int first = 1; first <= n; ++first) {
                // 知道perm的首个数据first便可得一组perm数据，此时判断1~n都出现了既为正确答案
                perm[0] = first;
                Map<Integer, Integer> record = new HashMap<Integer, Integer>();
                record.put(perm[0], record.getOrDefault(perm[0], 0) + 1);
                for (int i = 1; i < n; ++i) {
                    perm[i] = encoded[i - 1] ^ perm[i - 1];
                    record.put(perm[i], record.getOrDefault(perm[i], 0) + 1);
                }
                boolean flag = true;
                for (int i = 1; i <= n; ++i) {
                    if (!record.containsKey(i) || record.get(i) != 1) {
                        flag = false;
                    }
                }
                if (flag)
                    break;
            }
            return perm;
        }

        // n为奇数，encoded偶数个元素集合
        // encoded的奇数个元素求异或得perm数组除perm[0]以外所有元素的异或(x1^x2....^xn)
        // perm所有元素异或为1~n的异或(x0^x1^...^xn)
        public static int[] decodeTrue(int[] encoded) {
            int n = encoded.length + 1;
            int[] perm = new int[n];
            int temp = encoded[1];
            for (int i = 3; i < n; i += 2) {
                temp ^= encoded[i];
            }
            perm[0] = temp ^ sumXor(n);
            // for (int i = 1; i <= n; ++i) {
            // perm[0] ^= i;
            // }
            for (int i = 1; i < n; ++i) {
                perm[i] = encoded[i - 1] ^ perm[i - 1];
            }
            return perm;
        }

        // 利用异或的4i^(4i + 1)^(4i + 2)^(4i + 3) = 0特性实现单位时间内计算前n个数的异或结果
        public static int sumXor(int x) {
            if (x % 4 == 0) {
                return x;
            }
            if (x % 4 == 1) {
                return 1;
            }
            if (x % 4 == 2) {
                return x + 1;
            }
            return 0;
        }
    }

    public static class SolutionOfSearchInMatrix {
        /**
         * 判断某个矩阵中是否存在target这个目标值
         * 
         * 矩阵满足以下特性： 每一行的数字都从左到右排序；每一行的第一个数字都比上一行最后一个数字大
         * 
         * @param matrix int整型二维数组
         * @param target int整型
         * @return bool布尔型
         */
        // 把二维矩阵拉直相当于一个递增序列，因此采用二分法查找即可
        // 若一行最后一个元素小于target，则一定出现下面的行中
        // 可以考虑行二分加列二分，或者行列分开来判断，先确定在哪一行，再找该行中是否存在
        public boolean searchMatrix(int[][] matrix, int target) {
            int m = matrix.length;
            int n = matrix[0].length;
            int i = 0, j = n - 1;
            while (i < m && j >= 0) {
                if (matrix[i][j] == target) {
                    return true;
                } else if (matrix[i][j] > target) {
                    j--;
                } else {
                    i++;
                }
            }
            return false;
        }
    }

    public static class SolutionOfminNumberInRotateArray {
        /**
         * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转
         * 
         * 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素
         * 
         * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0
         * 
         * @param array
         * @return
         */
        // array为旋转后的数组，转后去的数一定小于前面的数
        public static int minNumberInRotateArray(int[] array) {
            int len = array.length;
            if (len == 0) {
                return 0;
            }
            int low = 0, high = len - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (array[mid] > array[high]) {
                    low = mid + 1;
                } else if (array[mid] < array[high]) {
                    high = mid;
                } else {
                    --high;
                }
            }
            return array[low];
        }
    }

    /**
     * 给你一个整数数组 bloomDay，以及两个整数 m 和 k
     * 
     * 现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花
     * 
     * 花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中
     * 
     * 请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1
     */
    public static int minDays(int[] bloomDay, int m, int k) {
        // 如果m * k <= bloomDay.length,则一定存在可制成花束的情形，否则一定不可能
        if (m * k > bloomDay.length) {
            return -1;
        }
        // 一定存在的情形，此时去寻找最少的天数，最少天数一定是1，最多天数一定是数组中的最大值
        // 因此我们枚举天数找到满足的最小值即可（>=res,一定可以实现；<res,一定不能实现）
        // 因此可以用二分思想：知道最少天数low = 1，最多天数high = max，找到最终结果res
        int low = 1, high = 1;
        for (int b : bloomDay) {
            high = Math.max(high, b);
        }
        while (low < high) {
            int day = (high - low) / 2 + low; // 中间值,记录当前等待的天数
            if (canMake(bloomDay, day, m, k)) {// 如果满足，将上限降低，再去判断
                high = day;
            } else {// 因为找的是最小值，所以对下限逐步提升
                low = day + 1;
            }
        }
        return low;
    }

    // 用来判断当前天数day是否满足条件
    public static boolean canMake(int[] bloomDay, int day, int m, int k) {
        int mLen = 0, flowers = 0, length = bloomDay.length;
        // 顺序判断，寻找满足的连续子数组（每个的bloomDay<=day,连起来的长度=k）
        for (int i = 0; i < length && mLen < m; ++i) {
            if (bloomDay[i] <= day) { // 开花+1
                ++flowers;
                if (flowers == k) {// 达到k朵，mLen+1
                    ++mLen;
                    flowers = 0; // 连续子数组个数置0
                }
            } else {// 否则重新开始计算连续子数组
                flowers = 0;
            }
        }
        return mLen >= m; // 连续子数组数大于m数则可以制作
    }

    public static class SolutionOfStackAndSort {
        /**
         * 栈排序
         * 
         * 给你一个1->n的排列和一个栈，入栈顺序给定,你要在不打乱入栈顺序的情况下，对数组进行从大到小排序
         * 
         * 当无法完全排序时，请输出字典序最大的出栈序列(xxx即尝试尽可能较大值先输出xxx，不是这个思路)
         * 
         * @param a int整型一维数组 描述入栈顺序
         * @return int整型一维数组
         */
        public static int[] solveMine(int[] a) {
            // 应该是将栈顶元素与之后的所有元素的最大值进行比较
            // 若当前栈顶值比后面的所有值都大，则它此时应该出栈（后进先出的特性，所以要保证后面进的不能比栈顶的大）
            int len = a.length, in = 0;
            int[] ans = new int[len];
            Stack<Integer> s = new Stack<Integer>();
            for (int i = 0; i < a.length; i++) {
                s.push(a[i]);
                while (!s.isEmpty() && isMax(s.peek(), i + 1, a)) {
                    ans[in++] = s.pop();
                }
            }
            while (!s.isEmpty()) {
                ans[in++] = s.pop();
            }
            return ans;
        }

        public static int[] solveTrue(int[] a) {
            if (a.length == 0)
                return a;
            Stack<Integer> stack = new Stack<Integer>();
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < a.length; i++) { // 先所有入栈
                stack.push(a[i]);
                while (!stack.isEmpty() && isMax(stack.peek(), i + 1, a)) {
                    // 如果出现isMax的情况则出栈，被记录下来
                    // 对栈顶元素都进行这样的处理，直到没有这种情况
                    list.add(stack.pop());
                }
            }
            while (!stack.isEmpty()) {
                list.add(stack.pop());
            }
            for (int i = 0; i < list.size(); i++)
                a[i] = list.get(i);
            return a;
        }

        public static boolean isMax(int n, int index, int[] a) {
            // isMax的判断，是将栈顶元素与之后的所有元素的最大值进行比较
            // 若当前栈顶值比后面的所有值都大，则它此时应该出栈
            for (int i = index; i < a.length; i++) {
                if (a[i] > n)
                    return false;
            }
            return true;
        }
    }

    /**
     * 有一个NxN整数矩阵，请编写一个算法，将矩阵顺时针旋转90度
     * 
     * 给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于300
     * 
     * @param mat
     * @param n
     * @return
     */
    public static int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        int out = n, in = 0, temp = 0;
        while (out > 0) {
            // 一层一层来
            // 0行->n-1列，n-1列->n-1行，n-1行->0列，0列->0行
            for (int i = in; i < out - 1; ++i) {
                temp = mat[in][i]; // 记录0行
                mat[in][i] = mat[n - 1 - i][in];// 0列->0行
                mat[n - 1 - i][in] = mat[n - 1 - in][n - 1 - i];// n-1行->0列
                mat[n - 1 - in][n - 1 - i] = mat[i][n - 1 - in];// n-1列->n-1行
                mat[i][n - 1 - in] = temp; // 0行->n-1列
            }
            out -= 1;
            in += 1;
        }
        return mat;
    }

    /**
     * 给你两个整数，n 和 start
     * 
     * 数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length
     * 
     * 请返回 nums 中所有元素按位异或（XOR）后得到的结果
     * 
     * @param n
     * @param start
     * @return
     */
    public static int xorOperation(int n, int start) {
        /**
         * 按照题意模拟即可：
         * 
         * 初始化 res = 0；
         * 
         * 遍历区间 [0, n - 1] 中的每一个整数 i，令 res 与每一个 start + 2 × i 做异或运算；
         * 
         * 最终返回 res
         */
        int res = start;
        for (int i = 1; i < n; ++i) {
            res = res ^ (start + 2 * i);
        }
        return res;
    }

    /**
     * 给出一组可能包含重复项的数字，返回该组数字的所有排列
     * 
     * @param num
     * @return
     */
    public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        boolean[] flag = new boolean[num.length];
        helper(num, new ArrayList<Integer>(), flag, result);

        return result;
    }

    public static void helper(int[] num, ArrayList<Integer> list, boolean[] flag,
            ArrayList<ArrayList<Integer>> result) {
        int size = list.size();
        if (num.length == size) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        ArrayList<Integer> temp = new ArrayList<>();// 同层去重
        for (int i = 0; i < num.length; i++) {
            if (flag[i])
                continue;
            if (i > 0 && num[i] == num[i - 1] && !flag[i - 1])
                continue;
            list.add(num[i]);
            temp.add(i);
            flag[i] = true;

            helper(num, list, flag, result);

            list.remove(size);
            flag[i] = false;
        }
    }

    /**
     * 未知 整数数组 arr 由 n 个非负整数组成
     * 
     * 经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1]
     * 例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3]（异或运算）
     * 
     * 给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）
     * 
     * 请解码返回原数组 arr 。可以证明答案存在并且是唯一的
     */
    public static int[] decode(int[] encoded, int first) {
        int len = encoded.length;
        int[] arr = new int[len + 1];
        arr[0] = first;
        // arr[1] ^ first = encoded[0], arr[1] ^ arr[2] = encoded[1]
        // arr[i](待求) ^ arr[i - 1](已知) = encoded[i - 1](已知),
        // 异或运算具有结合律 A XOR B XOR B = A XOR (B XOR B) = A XOR 0 = A
        // arr[i] = arr[i] ^ arr[i - 1] ^ arr[i - 1] = encoded[i - 1] ^ arr[i - 1]
        for (int i = 1; i < len + 1; ++i) {
            arr[i] = encoded[i - 1] ^ arr[i - 1];
        }
        return arr;
    }

    /**
     * 给你一个整数数组 nums ，你可以对它进行一些操作。
     * 
     * 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] +
     * 1 的元素。(注意：***此时的删除不获得点数)
     * 
     * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数
     */
    public static int deleteAndEarn(int[] nums) {
        // 选择删除某个数：所有的这个数都可以获得收益，因为其两侧数均被删除后续不会影响到该数
        // 确保获得点数收益（该数总和）大于删除其相邻值的和
        // 贪心？
        int maxres = 0, max = 0;
        Map<Integer, Integer> record = new HashMap<Integer, Integer>();
        for (int num : nums) {
            max = Math.max(max, num);
            record.put(num, record.getOrDefault(num, 0) + 1); // 记录相应的nums中的点数，并记录出现的次数
        }
        while (!record.isEmpty()) {
            for (int temp = 1; temp <= max; ++temp) {
                if (record.containsKey(temp)) {
                    // 针对当前值比较其收益和以及相邻值和
                    int tempSum = temp * record.get(temp), neighbourSum = 0;
                    if (record.containsKey(temp - 1)) {
                        // 包含上一个值
                        neighbourSum += (temp - 1) * record.get(temp - 1);
                    }
                    if (record.containsKey(temp + 1)) {
                        // 包含下一个值
                        neighbourSum += (temp + 1) * record.get(temp + 1);
                    }
                    if (tempSum > neighbourSum) { // 当前位置删除收益更高
                        System.out.println("nei" + neighbourSum);
                        System.out.println("temp" + tempSum);
                        record.replace(temp - 1, 0);
                        record.replace(temp + 1, 0);
                        record.remove(temp);
                        maxres += tempSum;
                        break;
                    }
                }
            }
        }
        return maxres;
    }

    public int deleteAndEarnTrue(int[] nums) {
        // 选择删除某个数：所有的这个数都可以获得收益，因为其两侧数均被删除后续不会影响到该数
        // 确保获得点数收益（该数总和）大于删除其相邻值的和
        // 贪心：当前数要不删，要不不删，判断删的收益高还是不删的收益高（类似于打家劫舍）
        if (nums == null || nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        }
        int len = nums.length;
        int max = nums[0];
        for (int i = 0; i < len; ++i) {
            max = Math.max(max, nums[i]); // 得到数组中的最大值
        }
        // 构造一个新的数组all，记录nums数组中每个数出现的次数
        // 并且作为当前删除的收益数组
        int[] all = new int[max + 1];
        for (int item : nums) {
            all[item]++;
        }
        int[] dp = new int[max + 1];
        dp[1] = all[1] * 1; // 到最大值为1的这个数收益
        dp[2] = Math.max(dp[1], all[2] * 2); // 到最大值为2的这个数收益
        // 动态规划求解
        for (int i = 2; i <= max; ++i) {
            // 当前数的收益：无收益，被上一数删除，收益为dp[i - 1];
            // 删除得收益，上一数被删除，收益为dp[i - 2] + i * all[i]
            // 类似于打家劫舍，相邻不被偷，上一家被偷此时不能偷，上一家未被偷，此时被偷
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * all[i]);
        }
        return dp[max];
    }

    /**
     * 给你一个n（1≤n≤10^5 ），和一个长度为n的数组，在不同时选位置相邻的两个数的基础上，求该序列的最大子序列和（挑选出的子序列可以为空）
     * 
     * @param n     int整型 数组的长度
     * @param array int整型一维数组 长度为n的数组
     * @return long长整型
     */
    public long subsequence(int n, int[] array) {
        // 如果前n项不相邻元素的子序列的和的最大值为a
        // 则前n+1项不相邻元素的子序列的和的最大值可能为前n-1项不相邻元素的子序列的和的最大值+第n项的数字，也可能还是等于如果前n项不相邻元素的子序列的和的最大值。
        // 取两者较大的就是前n+1项不相邻元素的子序列的和。
        // write code here
        int[] dp = new int[n]; // 创建与array大小相同的数组dp,第n个元素的位置用来存储前n项不相邻元素的最大子序列和
        // 如果array中只有一个元素，那么最大子序列和就是该元素的值
        dp[0] = array[0];
        // 如果array中有两个元素，那么最大子序列和是这两个元组中的最大值
        dp[1] = Math.max(dp[0], array[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 2] + array[i], dp[i - 1]);
        }
        return dp[n - 1];
    }

    /**
     * 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果
     * 
     * 如果反转后整数超过 32 位的有符号整数的范围 [−2^31,  2^31 − 1] ，就返回 0
     * 
     * 假设环境不允许存储 64 位整数（有符号或无符号）
     */
    public static int reverse(int x) { // x = 1534236469,会出现整数溢出,此时应该返回0
        StringBuffer s = new StringBuffer("" + x);
        int flag = 0;// 记录有无正负符号
        if (s.charAt(0) == '+') {
            flag = 1;
            s = s.deleteCharAt(0);
        }
        if (s.charAt(0) == '-') {
            flag = -1;
            s = s.deleteCharAt(0);
        }
        long temp = 0, max = 2147483647; // 用来处理整数溢出，max处理的是-2^31情况
        for (int i = s.length() - 1; i >= 0; --i) {
            temp = temp * 10 + (int) (s.charAt(i) - '0');
            System.out.println(temp);
        }
        if (flag == -1) {
            if (temp > max + 1) // 要大于-2147483648
                return 0;
            x = (int) (0 - temp);
            return x;
        }
        if (temp > 2147483647) // 大于2^31 - 1时返回0
            return 0;
        x = (int) temp;
        return x;
    }

    public int maxProfit2(int[] prices) {// 两次交易
        // 那就利用动态规划记录下来两次交易
        // write code here
        int n = prices.length;
        if (n < 2)
            return 0;
        int max = prices[n - 1];
        int[] f = new int[n];
        f[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--) {
            max = Math.max(max, prices[i]);
            f[i] = Math.max(f[i + 1], max - prices[i]);
        }
        int res = 0, min = prices[0];
        for (int i = 0; i < n - 1; i++) {
            min = Math.min(min, prices[i]);
            res = Math.max(res, prices[i] - min + f[i + 1]);
        }
        return res;
    }

    /**
     * 假设你有一个数组，其中第 i 个元素是股票在第 i 天的价格。
     * 你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。
     * 
     * @param prices int整型一维数组
     * @return int整型
     */
    public static int maxProfit1(int[] prices) {
        // write code here
        // 一次遍历实现
        int len = prices.length;
        if (len < 2)
            return 0;
        int buy = prices[0], profit = 0; // 一个尽可能小，一个尽可能大
        for (int i = 1; i < len; i++) {// 一次遍历同时判断两种情况
            // 尽量以最低价格买入，卖出时尽量收益要高
            // 因为只有一次买入和卖出
            // 当前价格更低，应该此时买入
            // 此时售出价格更高，应该此时售出
            buy = Math.min(buy, prices[i]);
            profit = Math.max(profit, prices[i] - buy);
        }
        return profit;
        // 多次循环遍历找最佳结果
        // int res = 0;
        // for (int i = 0; i < len - 1; ++i) {
        // for (int j = i + 1; j < len; ++j) {
        // res = Math.max(res, prices[j] - prices[i]);
        // }
        // }
        // return res;
    }

    /**
     * 你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和应该相等。
     * 
     * 你现在要画一条 自顶向下 的、穿过 最少
     * 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
     * 
     * 给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线
     * 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。
     * 
     */
    public static int leastBricksByHashMap(List<List<Integer>> wall) {
        // 首先明确完成的目标需要什么条件：
        // 每个位置存在的缝隙（砖的边界）
        // 利用hash表记录下0~sum[wall[i]]的每一个位置（边界）存在的缝隙和
        // 最后用n减去这个最大的缝隙和，即为最小的穿过数
        Map<Integer, Integer> cross = new HashMap<Integer, Integer>();
        for (List<Integer> widths : wall) {
            int temp = 0;
            for (int i = 0; i < widths.size() - 1; ++i) {
                temp += widths.get(i);
                cross.put(temp, cross.getOrDefault(temp, 0) + 1);// 存在该index位置的缝隙，加一，不存在设置为默认值为0，再加一
            }
        }
        int maxcross = 0;
        for (Map.Entry<Integer, Integer> entry : cross.entrySet()) { // 将HashMap中的数据成对取出
            maxcross = Math.max(maxcross, entry.getValue());
        }
        return wall.size() - maxcross;
    }

    public static int leastBricks(List<List<Integer>> wall) {
        int n = wall.size(); // cross穿过砖头数，sum一行总数，n列数
        int cross = n; // 穿过砖头数最多为列数n，先设定为一个最大值
        if (n == 0)
            return 0;
        // for (int i : wall.get(0))
        // sum += i;
        // for (int i = 1; i < sum; ++i) { // 从每一个位置暴力解决，判断每个位置的穿过砖头数
        // int temp = 0;
        // for (int j = 0; j < n; ++j) {
        // boolean flag = true;
        // int[] gap = new int[wall.get(j).size()]; // 记录缝隙
        // for (int m = 1; m < wall.get(j).size(); ++m)
        // gap[m] = gap[m - 1] + wall.get(j).get(m - 1);
        // for (int k = 1; k < gap.length; ++k) {
        // if (i == gap[k]) {
        // flag = false;
        // break;
        // }
        // }
        // if (flag)
        // ++temp;
        // }
        // cross = Math.min(cross, temp);
        // }
        // return cross;

        // 先记录下来每一层的缝隙
        List<List<Long>> gap = new ArrayList<List<Long>>();
        for (int i = 0; i < n; ++i) {
            List<Long> temp = new ArrayList<Long>();
            temp.add(0L);
            for (int j = 1; j < wall.get(i).size(); ++j) {
                temp.add(temp.get(j - 1) + wall.get(i).get(j - 1));
            }
            gap.add(temp);
        }
        for (int i = 0; i < n; ++i) { // 从每一层的间隙去解决，判断每个位置的穿过砖头数
            // 从间隙上往下寻找到的一定是最小的
            int temp = 0;
            for (int j = 1; j < gap.get(i).size(); ++j) {
                boolean flag = true;
                for (int l = i + 1; l < n; ++l) {
                    for (int m = 1; m < gap.get(l).size(); ++m) {
                        if (gap.get(i).get(j) == gap.get(l).get(m)) {
                            flag = false;
                            break;
                        }
                    }
                }
                if (flag)
                    ++temp;
            }
            cross = Math.min(cross, temp);
        }
        return cross;
    }

    /**
     * 请实现无重复数字的升序数组的二分查找
     * 
     * 给定一个 元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的
     * target，如果目标值存在返回下标，否则返回 -1
     *
     * 
     * @param nums   int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public static int search(int[] nums, int target) {
        // 采用二分查找的方式
        // write code here
        int len = nums.length;
        if (len == 0)
            return -1;
        int left = 0, right = len - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == nums[mid])
                return mid;
            else if (target < nums[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
        return -1;
    }

    /**
     * 
     * 一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
     * 
     * 1. 每个孩子不管得分多少，起码分到一个糖果。
     * 
     * 2.任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
     * 
     * 给定一个数组arr代表得分数组，请返回最少需要多少糖果。 [要求] 时间复杂度为On, 空间复杂度为O1
     * 
     * @param arr
     * @return
     */
    public static int candy(int[] arr) {
        // write code here
        // 左右两边顺序遍历一次，然后取两边得到的最大值，此时需要dp数组来记录
        // 因为单向比较无法保证回溯效果，所以若出现6 5 4 3 2 1得情况单向比较很难处理
        // 所以采用双向的dp，最后取对应位置的最大值
        int ans = 0;
        int N = arr.length;
        int[] left = new int[N], right = new int[N];
        left[0] = 1;// 初始条件
        for (int i = 1; i < N; ++i) {
            if (arr[i] > arr[i - 1]) // 若比前一位分数高，多分得一个糖果
                left[i] = left[i - 1] + 1;
            else // 若分数低，重新从最低个数1开始
                left[i] = 1;
        }
        right[N - 1] = 1;
        for (int i = N - 2; i >= 0; --i) {
            if (arr[i] > arr[i + 1])
                right[i] = right[i + 1] + 1;
            else
                right[i] = 1;
        }
        for (int i = 0; i < N; ++i)
            ans += Math.max(left[i], right[i]);
        return ans;
    }

    /**
     * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素
     * 
     * 1 <= nums.length <= 3 * 104, -231 <= nums[i] <= 231 - 1
     * 
     * 线性复杂度；无额外使用空间
     */
    public static int singleNumber(int[] nums) {
        Map<Integer, Integer> set = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (set.containsKey(num))
                set.replace(num, set.get(num), set.get(num) + 1);
            else
                set.put(num, 1);
        }
        for (int key : set.keySet()) {
            if (set.get(key) == 1)
                return key;
        }
        return 0;
    }

    public int singleNumberByBinary(int[] nums) { // 使用二进制表
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num : nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }

    class FSM {
        public int singleNumber(int[] nums) {
            int ones = 0, twos = 0;
            for (int num : nums) {
                ones = ones ^ num & ~twos;
                twos = twos ^ num & ~ones;
            }
            return ones;
        }
    }

    /**
     * max water
     * 
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public static long maxWater(int[] arr) {
        // write code here
        // 两边动态规划，最后求最小值
        int len = arr.length, res = 0;
        if (len < 3)
            return 0;
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = arr[0];
        right[len - 1] = arr[len - 1];
        // 从左遍历
        for (int i = 1; i < len; ++i)
            left[i] = Math.max(left[i - 1], arr[i]);
        // 从右遍历
        for (int i = len - 2; i >= 0; --i)
            right[i] = Math.max(right[i + 1], arr[i]);
        // 最后求最小值，要减去当前的arr高
        for (int i = 0; i < len; ++i)
            res += Math.min(right[i], left[i]) - arr[i];
        return res;
    }

    /**
     * 求最长回文子串的长度
     * 
     * @param A
     * @param n
     * @return
     */
    public int getLongestPalindrome(String A, int n) {
        // write code here
        char[] ch = A.toCharArray();
        int res = 0;
        for (int i = 0; i < n; i++) {// 采用的从某一位置向两边判断回文
            int l = i, r = i, sameR = i;
            // 定位左右两边,避免abba和aba，相同的移动位置
            while (l - 1 >= 0 && ch[l - 1] == ch[i])
                l--;
            while (r + 1 < n && ch[r + 1] == ch[i])
                r++;
            sameR = r; // sameR记录当前回文序列最长的地方，到某一位置不回文，则需要重新开始

            while (l - 1 >= 0 && r + 1 < n && ch[l - 1] == ch[r + 1]) {// 然后左右两边移动判断
                l--;
                r++;
            }

            res = Math.max(res, r - l + 1);

            // 优化，得到最长回文序列的地方再开始继续遍历
            i = sameR;
        }
        return res;
    }

    /**
     * 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c
     * 
     * @param c
     * @return
     */
    public static boolean judgeSquareSum(int c) {
        for (int i = 0; i <= (int) Math.sqrt(c); ++i) {
            if (Math.sqrt(c - i * i) == (int) Math.sqrt(c - i * i)) // 直接sqrt方法，比较开方后是否为整数
                return true;
        }
        return false;
    }

    public static boolean judgeSquareSumByDouIndex(int c) {
        // 双指针法，a，b一定是在0~Math.sqrt(c)之间的两个整数
        long left = 0; // 左指针
        long right = (long) Math.sqrt(c); // 右指针
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) { // sum == c时找到
                return true;
            } else if (sum > c) { // sum > c，b过大了，右指针减一
                right--;
            } else { // sum < c，a太小了，左指针加一
                left++;
            }
        }
        return false;
    }

    // 判断是否是完全平方数方法体
    public static boolean isSquare(int num) { // 开方判断法：把给出的num做开方运算判断，开方后的数字是不是整数。这里使用了try包裹住开方运算，是为了防止负数，也可以先加一步if判断实现相同的效果
        double a = 0;
        try {
            a = Math.sqrt(num);
        } catch (Exception e) {
            return false;
        }
        int b = (int) a;
        return a - b == 0;
    }

    // 这个方法超出了时间限制
    public static boolean advancedIsSquare(int num) {// 公式法：循环地减1、3、5……如果在某一个时刻值等于0，说明它是一个平方数。如果变成了负数，说明它不是平方数
        if (num < 0)
            return false;
        for (int i = 1; num > 0; i += 2)
            num -= i;
        return 0 == num;
    }

    public static boolean lowIsSquare(int num) {
        // 这种方法的思路是把比给出的目标数num小的整数都做一次平方运算，如果num等于某一个平方就返回true。这里做了一些优化，及不需要把小于num的数全部计算一次，只需要计算小于等于n的就可以
        if (num < 0)
            return false;
        for (int i = 0; i <= num / 2; i++) {
            if (i * i == num)
                return true;
        }
        return false;
    }

    /**
     * 假定你知道某只股票每一天价格的变动。 你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。
     * 请设计一个函数，计算你所能获得的最大收益。
     * 
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 计算最大收益
     * 
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public static int maxProfit(int[] prices) {
        // 主要思想：
        // 手上无彩票，与后一天比较，若涨价，买入必赚 flag == 0 && prices[i + 1] >= prices[i]
        // 手上无彩票，与后一天比较，若不涨价，按兵不动 flag == 0 && prices[i + 1] < prices[i]
        // 手上有彩票，与后一天比较，若涨价，按兵不动 flag == 1 && prices[i + 1] >= prices[i]
        // 手上有彩票，与后一天比较，若不涨价，卖出赚钱 flag == 1 && prices[i + 1] < prices[i]
        // write code here
        int res = 0, len = prices.length; // res记录最终的获利
        boolean flag = false; // 记录手上是否有股票
        if (len < 2)
            return res;
        for (int i = 0; i < len - 1; ++i) {
            if (!flag && prices[i + 1] >= prices[i]) { // 买入
                flag = true;
                res -= prices[i];
            }
            if (flag && prices[i + 1] < prices[i]) { // 卖出
                flag = false;
                res += prices[i];
            }
        } // 只遍历到倒数第二天
        if (flag) // 若最后一天手上还有彩票，卖出
            res += prices[len - 1];
        return res;
    }

    /**
     * 给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。
     * min edit cost
     * 
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic   int整型 insert cost
     * @param dc   int整型 delete cost
     * @param rc   int整型 replace cost
     * @return int整型
     */
    public static int minEditCost(String str1, String str2, int ic, int dc, int rc) {
        // write code here
        // str1 -> str2：替换 = 删除 + 插入；
        // 这对每一位：1、替换为想要字符；2、删除，下一位为想要字符；3、插入想要字符
        int[] res = new int[str2.length() + 1];
        int i, j, minres = Math.min(ic + dc, rc), leftTop, t;
        char[] c1 = str1.toCharArray(), c2 = str2.toCharArray();

        res[0] = 0;// 空数组代价为0

        for (i = 1; i <= c2.length; i++) // 初始代价为全部采用替换的方式
            res[i] = i * ic;// 替换i个字符，代价为i *ic

        for (i = 1; i <= c1.length; i++) {
            leftTop = res[0];
            res[0] = i * dc;
            for (j = 1; j <= c2.length; j++) {
                t = res[j];
                if (c1[i - 1] == c2[j - 1]) // 相同字符情况下
                    res[j] = leftTop;
                else
                    res[j] = Math.min(Math.min(res[j] + dc, res[j - 1] + ic), leftTop + minres); // 三种方式里最小的代价情况
                leftTop = t;
            }

        }
        return res[c2.length];
    }

    /**
     * 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。 传送带上的第
     * i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。 返回能在 D
     * 天内将传送带上的所有包裹送达的船的最低运载能力 必须顺序装运
     */
    public static int shipWithinDays(int[] weights, int D) {
        // 1 <= D <= weights.length <= 50000 1 <= weights[i] <= 500
        // 确定二分查找左右边界,数组中最大值left < 结果 res < 数组总和right
        int right = 0, left = 0; // 记录最大值，总值
        for (int w : weights) {
            right += w;
            left = Math.max(left, w);
        }
        while (left < right) {// 二分查找，最终结果一定在left和right之间
            int mid = (left + right) / 2;
            // need 为需要运送的天数
            // cur 为当前这一天已经运送的包裹重量之和
            int need = 1, cur = 0;
            for (int weight : weights) {
                if (cur + weight > mid) {
                    ++need;
                    cur = 0;
                }
                cur += weight;
            }
            if (need <= D) { // 需要运送天数小于D时，上限要减少
                right = mid;
            } else { // 否则就下限提高
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）
     */
    // public static int jumpFloor(int target) {
    // int[] dp = new int[target + 1];
    // dp[1] = 1;
    // dp[2] = 2;
    // for (int i = 3; i < target + 1; ++i) {
    // dp[i] = dp[i - 1] + dp[i - 2];
    // }

    // return dp[target];
    // }
    public static int jumpFloor(int target) {
        int l = 0, m = 1, r = 0;
        for (int i = 1; i < target + 1; ++i) {
            r = l + m;
            l = m;
            m = r;
        }

        return r;
    }

    /**
     * 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
     * 题目数据保证答案符合 32 位整数范围。 请注意，顺序不同的序列被视作不同的组合。 1 <= nums[i] <= 1000，1 <= target <=
     * 1000
     */
    public static int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1]; // dp数组记录等于target大小的元素组合的个数
        dp[0] = 1; // 假设target = 0时组合个数为1，边界条件,只有当不选取任何元素时，元素之和才为 0，因此只有 1 种方案
        for (int i = 1; i <= target; i++) { // 从1~target
            for (int num : nums) { // 再从数组中去寻找对应的组合值
                if (num <= i) { // 若num < i时可以加入组合
                    // 对于元素之和等于 i−num 的每一种排列，在最后添加num 之后即可得到一个元素之和等于 i 的排列，因此在计算 dp[i]
                    // 时，应该计算所有的dp[i−num] 之和
                    dp[i] += dp[i - num]; // 状态转移方程 dp[i] = dp[i] + dp[i - num]
                }
            }
        }
        return dp[target];
    }

    /**
     * 给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i],
     * answer[j]) 都应当满足： answer[i] % answer[j] == 0 ，或 answer[j] % answer[i] == 0
     * 如果存在多个有效解子集，返回其中任何一个均可。 nums 中的所有整数 互不相同
     */
    public static List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] f = new int[n]; // dp数组
        int[] g = new int[n]; // 记录数组，记录上一数的下标，得到最终子集
        for (int i = 0; i < n; i++) {
            // 至少包含自身一个数，因此起始长度为 1，由自身转移而来
            int len = 1, prev = i;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    // 如果能接在更长的序列后面，则更新「最大长度」&「从何转移而来」
                    if (f[j] + 1 > len) {
                        len = f[j] + 1;
                        prev = j;
                    }
                }
            }
            // 记录「最终长度」&「从何转移而来」
            f[i] = len;
            g[i] = prev;
        }

        // 遍历所有的 f[i]，取得「最大长度」和「对应下标」
        int max = -1, idx = -1;
        for (int i = 0; i < n; i++) {
            if (f[i] > max) {
                idx = i;
                max = f[i];
            }
        }

        // 使用 g[] 数组回溯出具体方案
        List<Integer> ans = new ArrayList<>();
        while (ans.size() != max) {
            ans.add(nums[idx]);
            idx = g[idx];
        }
        return ans;
    }

    /**
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
     * 
     * 例子: -2 1 -3 4 -1 2 1 -5 4； -1 -2 dp： -2 1 1 4 4 5 6 6 6； -1 -1 sum： -2 1 -2 4
     * 3 5 6 1 5； -1 -2
     * 
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums) {
        // 主要思路：不小于零的部分就可以加上，增大连续子数组的大小
        int len = nums.length, sum, dp; // sum是用来记录所选择的子序列到当前位置的相加和，dp用来记录当前数组处能有的最大连续子数组和
        dp = sum = nums[0];
        for (int i = 1; i < len; ++i) {
            if (sum < 0) { // 前面的值加起来小于0，另起炉灶
                sum = nums[i]; // sum重新开始相加
                dp = Math.max(dp, nums[i]);// dp为max(前面部分连续子数组和，nums[i]重新开始)
            } else {
                dp = Math.max(dp, sum + nums[i]);// 前面部分相加不小于0，就可以加上
                sum += nums[i]; // 然后sum把整个数组序列相加上
            }
        }
        return dp;
    }

    class SolutionOfnumDecodings {
        public int numDecodings(String s) {
            int n = s.length();
            int[] f = new int[n + 1]; // 初始dp数组值全为0
            f[0] = 1;
            for (int i = 1; i <= n; ++i) {
                if (s.charAt(i - 1) != '0') {
                    f[i] += f[i - 1]; // 所以这里采用的相加的形式f[i]在这里永远是0的情况
                }
                if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                    f[i] += f[i - 2];
                }
            }
            return f[n];// 若出现没办法解码的情况，得到的f[n] = 0
        }
    }

    /**
     * A-Z映射1-26，解码已编码的字符串信息s，返回解码方法的总数，如“11106”可解码成“AAJF”（1 1 10 6）或“KJF”（11 10 6）
     * 含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20",即0的前一位数只能为1或者2
     * 
     * ASCII码：A-Z:65-90; 故对应相隔64 (char) (映射 + 64),对应关系只用来找出哪些对应的解码结果
     * 
     * @param s
     * @return
     */
    public static int numDecodings(String s) {
        char[] ch = s.toCharArray();
        int len = ch.length;
        int l = 0, m = 0, r = 0;
        // 边界条件处理
        if (ch[0] == '0')
            return 0;
        else {
            if (len == 1)
                return 1;
            else {
                if (ch[0] - '0' > 2 && ch[1] == '0')
                    return 0;
                if (ch[1] == '0') {
                    l = 1;
                    m = 1;
                } else {
                    if (ch[0] == '1' || ch[0] == '2' && ch[1] - '0' <= 6) {
                        l = 1;
                        m = 2;
                    } else {
                        l = 1;
                        m = 1;
                    }
                }
            }
        }
        // 动态规划过程
        for (int i = 2; i < len; ++i) {
            if (ch[i] - '0' == 0) {
                if (ch[i - 1] - '0' == 1 || ch[i - 1] - '0' == 2)
                    r = l;
                else
                    return 0;
            } else {
                if (ch[i - 1] - '0' == 0 || ch[i - 1] - '0' > 2 || ch[i - 1] - '0' == 2 && ch[i] - '0' > 6)
                    r = m;
                else {
                    if (ch[i - 2] - '0' == 0) {
                        if (ch[i - 1] - '0' == 2 && ch[i] - '0' > 6)
                            return 0;
                        r = 2 * m;
                    } else
                        r = m + l;
                }
            }
            l = m;
            m = r;
        }
        if (len == 1)
            return l;
        if (len == 2)
            return m;
        return r;
    }

    /**
     * 两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0
     * 开始）。如果不存在，则返回  -1 如果needle为空字符串返回0
     * 
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr(String haystack, String needle) {// 这个题目其实直接调用indexOf()函数便可以实现
        int m = haystack.length(), n = needle.length();
        char[] hay = haystack.toCharArray();
        char[] need = needle.toCharArray();
        for (int i = 0; i <= m - n; ++i) {
            int a = i, b = 0;
            while (b < n && hay[a] == need[b]) {// 一旦出现不匹配直接结束继续比较
                ++a;
                ++b;
            }
            if (b == n)
                return i;
        }
        return -1;
    }

    // 但是若只是这样的话根本起不到学习算法的效果，匹配问题想到KMP算法
    // KMP 算法
    // ss: 原串(string) pp: 匹配串(pattern)
    public int strStrByKMP(String ss, String pp) {
        if (pp.isEmpty())
            return 0;

        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m + 1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1])
                j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1])
                j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }

        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1])
                j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1])
                j++;
            // 整一段匹配成功，直接返回下标
            if (j == m)
                return i - m;
        }

        return -1;
    }

    /**
     * 对于一个给定的字符串，在线性(也就是O(n))的时间里对它做一些变形。 首先这个字符串中包含着一些空格，就像"Hello
     * World"一样，然后我们要做的是把着个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。 比如"Hello World"变形后就变成了"wORLD
     * hELLO"。
     * 
     * @param s
     * @param n
     * @return
     */
    public static String trans(String s, int n) {
        // write code here
        String[] temp = s.split(" ");
        String res = "";
        for (int i = 0; i < temp.length; ++i) {
            char[] word = temp[i].toCharArray();
            for (int j = 0; j < word.length; ++j) {
                if (word[j] >= 'A' && word[j] <= 'Z') {
                    word[j] += 32;
                } else if (word[j] >= 'a' && word[j] <= 'z') { // 如果输入的是小写，-32即可得大小写
                    word[j] -= 32;
                }
            }
            res = " " + String.valueOf(word) + res;// 得到的结果是比正确结果多出一个最前面的空格
        }
        // n是用保证字符串的长度正确，例如"h i "和4就存在一个空格数，字符串总长度为4
        if (res.length() == n)// 若有有多余的一个空格，则多添加的最前面的一个空格正好保证了res长度为n，故直接返回
            return res;
        return res.substring(1); // 若无多余的空格，则把最前面部分的空格去除掉
    }

    /**
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用
     * O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     */
    public static int removeElement(int[] nums, int val) {
        int len = nums.length, slow = 0, fast = len - 1;
        if (len == 0 || len == 1 && nums[0] == val)
            return 0;
        if (len == 1 && nums[0] != val)
            return 1;
        while (slow <= fast) { // 要保证到slow==fast的情况，因为会出现最后slow和fast指向的值都不等于val
            if (nums[slow] == val) {
                while (nums[fast] == val && fast >= slow) { // 保证fast不会越过slow的边界
                    --fast;
                    if (fast == slow) // 全部为val值，这个确保最后得到的nums为空
                        break;
                }
                nums[slow] = nums[fast--];
            } else
                ++slow;
        }
        return slow;
    }

    /**
     * 比较版本号
     * 
     * 版本号是由修订号组成，修订号与修订号之间由一个"."连接。1个修订号可能有多位数字组成，修订号可能包含前导0，且是合法的。
     * 例如，1.02.11，0.1，0.2都是合法的版本号 每个版本号至少包含1个修订号。
     * 修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。
     * 比较规则：一.比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如"0.1"和"0.01"的版本号是相等的
     * 二.如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，"1.1"的版本号小于"1.1.1"。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1
     * 三. version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.
     * 
     * @param version1 string字符串
     * @param version2 string字符串
     * @return int整型
     */
    public static int compare(String version1, String version2) {
        // write code here
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int len1 = v1.length, len2 = v2.length;
        if (len1 < len2) {
            for (int i = 0; i < len1; ++i) {
                if (Integer.parseInt(v1[i]) > Integer.parseInt(v2[i]))
                    return 1;
                else if (Integer.parseInt(v1[i]) < Integer.parseInt(v2[i]))
                    return -1;
            }
            // 最主要是这里的情况，会存在version1 = "1.0", version2 = "1.0.0"
            // 这时不仅要比较前述情况，后续还要判断version2多出的部分是否全为0（相等），不全为0返回-1
            for (int i = len1; i < len2; ++i) {
                if (Integer.parseInt(v2[i]) > 0)
                    return -1;
            }
            return 0;
        } else if (len1 > len2) {
            for (int i = 0; i < len2; ++i) {
                if (Integer.parseInt(v1[i]) > Integer.parseInt(v2[i]))
                    return 1;
                else if (Integer.parseInt(v1[i]) < Integer.parseInt(v2[i]))
                    return -1;
            }
            return 1;
        } else {
            for (int i = 0; i < len1; ++i) {
                if (Integer.parseInt(v1[i]) > Integer.parseInt(v2[i]))
                    return 1;
                else if (Integer.parseInt(v1[i]) < Integer.parseInt(v2[i]))
                    return -1;
            }
        }
        return 0;
    }

    public static int compare2(String version1, String version2) {
        // write code here
        // 比较两个字符串的大小，从非0开始，然后往后比较
        // 考虑 以.为分界线，依次比较大小
        int index1 = 0, index2 = 0;
        int len1 = version1.length(), len2 = version2.length();
        while (index1 < len1 || index2 < len2) {
            if (index1 < len1 && version1.charAt(index1) == '.') {
                index1++;
            }
            if (index2 < len2 && version2.charAt(index2) == '.') {
                index2++;
            }
            int res1 = 0, res2 = 0;
            // 这里拼接数字
            while (index1 < len1 && version1.charAt(index1) != '.') {
                if (version1.charAt(index1) == '0') {
                    index1++;
                } else {
                    res1 = res1 * 10 + version1.charAt(index1++) - '0';
                }
            }
            while (index2 < len2 && version2.charAt(index2) != '.') {
                if (version2.charAt(index2) == '0') {
                    index2++;
                } else {
                    res2 = res2 * 10 + version2.charAt(index2++) - '0';
                }
            }
            if (res1 != res2) {
                return res1 > res2 ? 1 : -1;
            }
        }
        return 0;
    }

    /**
     * 有序数组 nums ，原地(不使用额外的数组空间)删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度
     * 
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len < 1)
            return len;
        int slow = 1, fast = 1;
        while (fast < len) {
            if (nums[slow - 1] != nums[fast]) {
                nums[slow++] = nums[fast];
            }
            ++fast;
        }
        return slow;
    }

    /**
     * 整数数组 nums 和两个整数 k 和 t 判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t
     * ，同时又满足 abs(i - j) <= k 如果存在则返回 true，不存在返回 false。
     * 
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        Set<Long> set = new HashSet<Long>();
        int len = nums.length;
        if (len < 2)
            return false;
        for (int i = 0; i < len; ++i) {
            // nums[i] +- t 范围内存在数即为true,出现整数越界，使用long型（但会出现超时情况）
            for (long j = (long) nums[i] - t; j <= (long) nums[i] + t; ++j) {
                if (set.contains((long) j))
                    return true;
            }
            set.add((long) nums[i]);
            if (set.size() > k) {
                set.remove((long) nums[i - k]);// 如果当前散列表的大小超过了 k， 删除散列表中最旧的元素
            }
        }
        return false;
    }

    public static boolean containsNearbyAlmostDuplicateByTreeSet(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<Long>();// 有序集合，使用红黑树来存储内部元素
        for (int i = 0; i < n; i++) {
            // Returns the least（最小的） element in this set greater than or equal to the given
            // element, or null if there is no such element.
            // 返回大于或等于所给元素的最小值，若不存在返回为空
            Long ceiling = set.ceiling((long) nums[i] - (long) t);
            // 找到TreeSet中大于或等于所给元素的值，若返回不为空，且在 nums[i] - t ~ nums[i] + t范围内，返回true
            if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {
                return true;
            }
            set.add((long) nums[i]);
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;
    }

    public static boolean containsNearbyAlmostDuplicateByTong(int[] nums, int k, int t) {
        int n = nums.length;
        Map<Long, Long> map = new HashMap<Long, Long>();
        long w = (long) t + 1;
        for (int i = 0; i < n; i++) {
            long id = getID(nums[i], w);
            if (map.containsKey(id)) {
                return true;
            }
            if (map.containsKey(id - 1) && Math.abs(nums[i] - map.get(id - 1)) < w) {
                return true;
            }
            if (map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w) {
                return true;
            }
            map.put(id, (long) nums[i]);
            if (i >= k) {
                map.remove(getID(nums[i - k], w));
            }
        }
        return false;
    }

    public static long getID(long x, long w) {
        if (x >= 0) {
            return x / w;
        }
        return (x + 1) / w - 1;
    }

    /**
     * 给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1) 最大乘积
     * 
     * @param A int整型一维数组
     * @return long长整型
     */
    public static long solve(int[] A) {
        // write code here
        int len = A.length;
        if (len < 3)
            return 0;
        if (len == 3)
            return A[0] * A[1] * A[2];
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        for (int i = 0; i < A.length; i++) {
            if (A[i] < min1) {// 更新最小值
                min2 = min1;
                min1 = A[i];
            } else if (A[i] < min2) {// 更新第二小
                min2 = A[i];
            }
            if (A[i] > max1) {// 更新最大值
                max3 = max2;
                max2 = max1;
                max1 = A[i];
            } else if (A[i] > max2) {// 更新第二大
                max3 = max2;
                max2 = A[i];
            } else if (A[i] > max3) {// 更新第三大
                max3 = A[i];
            }
        }
        // 要转换成long型
        return Math.max(((long) max1 * max2 * max3), ((long) max1 * min1 * min2));
    }

    /**
     * 给定一个整数数组和一个整数 k 判断数组中是否存在两个不同的索引 i 和 j 使得 nums [i] = nums [j]，并且 i 和
     * j 的差的绝对值至多为 k。
     */
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k == 0 || nums.length == 0)
            return false;
        for (int i = 0; i < nums.length - 1; ++i) {
            for (int j = i + 1; j <= i + k && j < nums.length; ++j) {
                if (nums[i] == nums[j])
                    return true;
            }
        }
        return false;
    }

    public boolean containsNearbyDuplicateByHashSet(int[] nums, int k) {
        Set<Integer> set = new HashSet<>(); // 利用散列表
        for (int i = 0; i < nums.length; ++i) {
            if (set.contains(nums[i]))
                return true;
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }

    public static String largestNumber(int[] nums) {
        ArrayList<String> numToStr = new ArrayList<>();
        int len = nums.length;
        String res = "";
        for (int i = 0; i < len; ++i) {
            numToStr.add(Integer.toString(nums[i]));
        }
        numToStr.sort(Comparator.reverseOrder());
        for (String str : numToStr) {
            System.out.println(str);
        }
        return res;
    }

    public static int lengthOfLIS(int[] nums) {
        int len = nums.length, r;
        if (len == 0)
            return 0;
        int[] dp = new int[len];
        int maxres = 1;
        for (int i = 1; i < len; ++i) {
            r = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    r = Math.max(r, dp[j] + 1);
                }
            }
            maxres = Math.max(maxres, r);
        }
        return maxres;
    }

    public static int lengthOfLISByGreedy(int[] nums) {
        int len = 1, n = nums.length;
        if (n == 0)
            return 0;
        int[] d = new int[n + 1];
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0;// 二分查找，如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }

    // 将字符串转换成int数值，要考虑各种情形
    public static int atoi(String str) {
        if (str == null || str.trim().length() < 1)
            return 0;

        char[] arr = str.trim().toCharArray(); // 将字符串转换成字符数组，方便对每一个字符进行操作

        int index = 0, flag = 1; // index用来判断是否存在符号，flag判断正负
        if (arr[0] == '+')
            ++index;
        if (arr[0] == '-') {
            ++index;
            flag = -1;
        }

        int num = 0;
        for (int i = index; i < arr.length; ++i) {
            if (arr[i] - '0' >= 0 && arr[i] - '9' <= 0) {
                if (num > Integer.MAX_VALUE / 10 || num == Integer.MAX_VALUE / 10 && arr[i] - '7' > 0) {
                    if (flag > 0)
                        return Integer.MAX_VALUE;
                    else
                        return Integer.MIN_VALUE;
                }

                num = 10 * num + arr[i] - '0';
            } else {
                // 字母直接跳出循环
                break;
            }
        }
        return num * flag;
    }
}